{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Degree of a Connected Trio in a Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minTrioDegree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #一个图中连通三元组的最小度数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个无向图，整数 <code>n</code> 表示图中节点的数目，<code>edges</code> 数组表示图中的边，其中 <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> ，表示 <code>u<sub>i</sub></code> 和 <code>v<sub>i</sub></code><sub> </sub>之间有一条无向边。</p>\n",
    "\n",
    "<p>一个 <strong>连通三元组</strong> 指的是 <strong>三个</strong> 节点组成的集合且这三个点之间 <strong>两两</strong> 有边。</p>\n",
    "\n",
    "<p><strong>连通三元组的度数</strong> 是所有满足此条件的边的数目：一个顶点在这个三元组内，而另一个顶点不在这个三元组内。</p>\n",
    "\n",
    "<p>请你返回所有连通三元组中度数的 <strong>最小值</strong> ，如果图中没有连通三元组，那么返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/02/14/trios1.png\" style=\"width: 388px; height: 164px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>只有一个三元组 [1,2,3] 。构成度数的边在上图中已被加粗。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/02/14/trios2.png\" style=\"width: 388px; height: 164px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>有 3 个三元组：\n",
    "1) [1,4,3]，度数为 0 。\n",
    "2) [2,5,6]，度数为 2 。\n",
    "3) [5,6,7]，度数为 2 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= n <= 400</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>1 <= edges.length <= n * (n-1) / 2</code></li>\n",
    "\t<li><code>1 <= u<sub>i</sub>, v<sub>i</sub> <= n</code></li>\n",
    "\t<li><code>u<sub>i </sub>!= v<sub>i</sub></code></li>\n",
    "\t<li>图中没有重复的边。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-degree-of-a-connected-trio-in-a-graph](https://leetcode.cn/problems/minimum-degree-of-a-connected-trio-in-a-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-degree-of-a-connected-trio-in-a-graph](https://leetcode.cn/problems/minimum-degree-of-a-connected-trio-in-a-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n[[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]', '7\\n[[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        if n < 3:\n",
    "            return -1\n",
    "        has_edges = [[False]*(n+1) for _ in range(n+1)]\n",
    "        degrees = [0] * (n+1)\n",
    "        for [i, j] in edges:\n",
    "            has_edges[i][j] = True\n",
    "            has_edges[j][i] = True\n",
    "            degrees[i] += 1\n",
    "            degrees[j] += 1\n",
    "        \n",
    "        ans = len(edges)\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(j+1, n+1):\n",
    "                    if has_edges[i][j] and has_edges[j][k] and has_edges[k][i]:\n",
    "                        ans = min(ans, degrees[i]+degrees[j]+degrees[k]-6)\n",
    "\n",
    "        if ans == len(edges):\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        \n",
    "        has_edges = [[False]*(n+1) for _ in range(n+1)]\n",
    "        degrees = [0] * (n+1)\n",
    "        for [i, j] in edges:\n",
    "            has_edges[i][j] = True\n",
    "            has_edges[j][i] = True\n",
    "            degrees[i] += 1\n",
    "            degrees[j] += 1\n",
    "        \n",
    "        ans = float('inf')\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(j+1, n+1):\n",
    "                    if has_edges[i][j] and has_edges[j][k] and has_edges[k][i]:\n",
    "                        ans = min(ans, degrees[i]+degrees[j]+degrees[k]-6)\n",
    "\n",
    "        return -1 if ans == float('inf') else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ind={i:0 for i in range(1,n+1)}\n",
    "        dis= [[0]*(n+1) for _ in range(n+1)]\n",
    "        for s,e in edges:\n",
    "            dis[s][e]=1\n",
    "            dis[e][s]=1\n",
    "            ind[e]+=1\n",
    "            ind[s]+=1\n",
    "        mx=float(\"inf\")\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i+1,n+1):\n",
    "                for k in range(j+1,n+1):\n",
    "                    if dis[i][j]==1 and dis[j][k]==1 and dis[k][i]==1:\n",
    "                        total=ind[i]+ind[j]+ind[k]-6\n",
    "                        mx=min(total,mx)\n",
    "        if mx==float(\"inf\"):\n",
    "            return -1\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        links = [[0] * n for _ in range(n)]  # 标记任意两个节点之间是否有连接\n",
    "        degrees = [0] * n     # 表示每个节点连接的边数\n",
    "        for e in edges:\n",
    "            x, y = e[0] - 1, e[1] - 1   # 节点索引的能够与节点编号-1\n",
    "            links[x][y] = links[y][x] = 1  # 标记两个节点之间存在连接\n",
    "            degrees[x] += 1   # 两个节点的度都增加1\n",
    "            degrees[y] += 1\n",
    "        res = n * n    # 结果，初始化为一个不可能的值\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if links[i][j] == 0: continue   # 两个节点之间不存在连接跳过\n",
    "                for k in range(j + 1, n):\n",
    "                    if links[i][k] == 0 or links[j][k] == 0: continue   # 三个节点之间存在不连接的两个节点，跳过\n",
    "                    res = min(res, degrees[i] + degrees[j] + degrees[k] - 6)  # 找到一个连通三元组，更新最小度\n",
    "\n",
    "        return -1 if res == n*n else res   # res没有变化说明没有不存在三元组返回-1\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        degree = [0] * n\n",
    "        \n",
    "        for x, y in edges:\n",
    "            x, y = x - 1, y - 1\n",
    "            g[x][y] = g[y][x] = 1\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if g[i][j] == 1:\n",
    "                    for k in range(j + 1, n):\n",
    "                        if g[i][k] == g[j][k] == 1:\n",
    "                            ans = min(ans, degree[i] + degree[j] + degree[k])\n",
    "        \n",
    "        return -1 if ans == inf else ans-6\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        degree = [0] * n\n",
    "        \n",
    "        for x, y in edges:\n",
    "            x, y = x - 1, y - 1\n",
    "            g[x][y] = g[y][x] = 1\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if g[i][j] == 1:\n",
    "                    for k in range(j + 1, n):\n",
    "                        if g[i][k] == g[j][k] == 1:\n",
    "                            ans = min(ans, degree[i] + degree[j] + degree[k] - 6)\n",
    "        \n",
    "        return -1 if ans == inf else ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # adjList = [set() for _ in range(n + 1)]\n",
    "        # adj = [[False for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        # degree = [0 for _ in range(n + 1)]\n",
    "        # for u, v in edges :\n",
    "        #     adj[u][v] = True\n",
    "        #     adj[v][u] = True\n",
    "        #     degree[u] += 1\n",
    "        #     degree[v] += 1\n",
    "        # res = inf\n",
    "        # for i in range(1, n + 1) :\n",
    "        #     for j in range(i + 1, n + 1) :\n",
    "        #         if adj[i][j] :\n",
    "        #             for k in range(j + 1, n + 1) :\n",
    "        #                 if adj[i][k] and adj[j][k] :\n",
    "        #                     if res > (tmp := degree[i] + degree[j] + degree[k] - 6) :\n",
    "        #                         res = tmp\n",
    "        # return res if res != inf else - 1\n",
    "\n",
    "\n",
    "        # adjList = [[] for _ in range(n + 1)]\n",
    "        # degree = [0 for _ in range(n + 1)]\n",
    "        # s = set()\n",
    "        # for u, v in edges :\n",
    "        #     if degree[u] < degree[v] or (degree[u] == degree[v] and u < v) :\n",
    "        #         adjList[u].append(v)\n",
    "        #     else :\n",
    "        #         adjList[v].append(u)\n",
    "        #     degree[u] += 1\n",
    "        #     degree[v] += 1\n",
    "        #     s.add((u, v))\n",
    "        #     s.add((v, u))\n",
    "        # res = inf \n",
    "        # for i in range(1, n + 1) :\n",
    "        #     for j in adjList[i] :\n",
    "        #         for k in adjList[j] :\n",
    "        #             if (i, k) in s:\n",
    "        #                 if res > (tmp := degree[i] + degree[j] + degree[k] - 6) :\n",
    "        #                     res = tmp   \n",
    "        #     if res == 0 :\n",
    "        #         return 0  \n",
    "        # return -1 if res == inf else res\n",
    "\n",
    "\n",
    "        adj = defaultdict(list)\n",
    "        degree = defaultdict(int)\n",
    "        for u, v in edges :\n",
    "            adj[u].append(v)\n",
    "            adj[v].append(u)\n",
    "            degree[u] += 1\n",
    "            degree[v] += 1\n",
    "        res = inf\n",
    "        adjList = dict(sorted(adj.items(), key = lambda x : degree[x[0]]))\n",
    "        for _, l in adjList.items() :\n",
    "            l.sort(key = lambda x : degree[x])\n",
    "        print(adjList)\n",
    "        def func(i) :\n",
    "            for j in adjList[i] :\n",
    "                for k in adjList[j] :\n",
    "                    if k in adjList[i] :\n",
    "                        return degree[i] + degree[j] + degree[k] - 6\n",
    "            return inf\n",
    "        for i in adjList.keys() :\n",
    "            if degree[i] < 2 :\n",
    "                continue\n",
    "            if res > (tmp := func(i)) :\n",
    "                res = tmp\n",
    "            if res == 0 :\n",
    "                return 0\n",
    "        return -1 if res == inf else res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        degree = defaultdict(int)\n",
    "        neighbour = defaultdict(list)\n",
    "        matrix = [[0] * n for _ in range(n)]\n",
    "        for src, dst in edges:\n",
    "            degree[src] += 1\n",
    "            degree[dst] += 1\n",
    "            neighbour[src].append(dst)\n",
    "            neighbour[dst].append(src)\n",
    "            matrix[src - 1][dst - 1] = 1\n",
    "            matrix[dst - 1][src - 1] = 1\n",
    "\n",
    "        for data in neighbour.values():\n",
    "            data.sort(key=lambda x: degree[x])\n",
    "        # print(neighbour)\n",
    "        order = sorted(degree.keys(), key=lambda x: degree[x])\n",
    "        # print(degree, order)\n",
    "\n",
    "        res = float(\"inf\")\n",
    "        for i in range(len(order)):\n",
    "            x = order[i]\n",
    "            if degree[x] * 3 - 6 >= res:\n",
    "                break\n",
    "\n",
    "            if degree[x] < 2:\n",
    "                continue\n",
    "\n",
    "            for j in range(len(neighbour[x])):\n",
    "                y = neighbour[x][j]\n",
    "                if degree[y] * 2 + degree[x] - 6 >= res:\n",
    "                    break\n",
    "                \n",
    "                if y not in neighbour[x]:\n",
    "                    continue\n",
    "                \n",
    "                for k in range(j + 1, len(neighbour[x])):\n",
    "                    z = neighbour[x][k]\n",
    "                    if degree[x] + degree[y] + degree[z] - 6 >= res:\n",
    "                        break\n",
    "\n",
    "                    if matrix[y - 1][z - 1] == 1:\n",
    "                        res = min(res, degree[x] + degree[y] + degree[z] - 6)\n",
    "                        break\n",
    "\n",
    "        return res if res != float(\"inf\") else -1\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        maps = collections.defaultdict(list)\n",
    "\n",
    "        def is_trio(key, l , maps):\n",
    "            for i in l:\n",
    "                for j in maps[i]:\n",
    "                    if key in maps[j]:\n",
    "                        degree = len(maps[i]) + len(maps[j]) + len(maps[key]) - 6\n",
    "                        print(i,j,key,degree)\n",
    "                        return degree\n",
    "            return float('inf')\n",
    "                 \n",
    "            \n",
    "        for s, e in edges:\n",
    "            maps[s].append(e)\n",
    "            maps[e].append(s)\n",
    "        res = float('inf')\n",
    "        maps = dict(sorted(maps.items(),key=lambda x : len(x[1])))\n",
    "        maps ={key:sorted(value,key=lambda x : len(maps[x])) for key,value in maps.items()}\n",
    "        print(maps)\n",
    "        for i in maps.keys():\n",
    "            if len(maps[i]) < 2:\n",
    "                continue\n",
    "            deg = is_trio(i, maps[i], maps)\n",
    "            if deg == 0:\n",
    "                res = deg\n",
    "                break\n",
    "            elif deg < res:\n",
    "                res = deg\n",
    "        if res == float('inf'):\n",
    "            return -1\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        degree = [0] * (n)\n",
    "        gra = defaultdict(list)\n",
    "        sortedg = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            u,v = u-1, v-1\n",
    "            gra[u].append(v)\n",
    "            gra[v].append(u)\n",
    "            degree[u] += 1\n",
    "            degree[v] += 1\n",
    "        arr = list(range(n))\n",
    "        arr.sort(key = lambda x:len(gra[x]))\n",
    "        for u, v in edges:\n",
    "            u, v = u-1, v-1\n",
    "            if degree[u] < degree[v] or (degree[u] == degree[v] and u <v):\n",
    "                sortedg[u].append(v)\n",
    "            else:\n",
    "                sortedg[v].append(u)\n",
    "        ans  = float('inf')\n",
    "\n",
    "        for i in arr:\n",
    "            if len(gra[i]) < 2:\n",
    "                continue\n",
    "            for j in sortedg[i]:\n",
    "                for k in sortedg[j]:\n",
    "                    if k in gra[i]:   #connected three vertex)\n",
    "                        ans = min(ans, degree[i] + degree[j] + degree[k]\n",
    "                         -6)\n",
    "                        if degree[i] >= n-1: return ans\n",
    "        return ans if ans != inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 三角形 lcp16\n",
    "        # 无向图变成有向图  边从小指向大\n",
    "        ans = inf\n",
    "        g = defaultdict(set)\n",
    "        cnt = Counter()   # 度 \n",
    "        for a, b in edges:\n",
    "            if a > b:\n",
    "                a, b = b, a \n",
    "            g[a].add(b)\n",
    "            cnt[a] += 1\n",
    "            cnt[b] += 1\n",
    "        # 三角形枚举两个点 i,j,k 严格递增\n",
    "        # 下面的遍历满足 i<j<k\n",
    "        for i in range(1, n+1):\n",
    "            for j in g[i]:\n",
    "                k_choose = g[i] & g[j]\n",
    "                for k in k_choose:\n",
    "                    ans = min(ans, cnt[i] + cnt[j] + cnt[k] - 6)\n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(lambda: defaultdict(int))\n",
    "        for i, j in edges:\n",
    "            g[i][0] += 1\n",
    "            g[j][0] += 1\n",
    "            g[i][j] += 1\n",
    "            g[j][i] += 1\n",
    "        result = float('inf')\n",
    "        for i in g:\n",
    "            if len(g[i]) < result:\n",
    "                for j in filter(lambda j: j > i, g[i]):\n",
    "                    for k in filter(lambda k: k > j, g[j]):\n",
    "                        if k in g[i]:\n",
    "                            result = min(result, g[i][0] + g[j][0] + g[k][0])\n",
    "        return result - 6 if result < float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 节点优化过的关联的节点set\n",
    "        edge_l = [set() for _ in range(n + 1)]\n",
    "        # 节点的边数\n",
    "        no_l = [0] * (n + 1)\n",
    "        res = n * 3\n",
    "        for a, b in edges:\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            edge_l[a].add(b)\n",
    "            no_l[a] += 1\n",
    "            no_l[b] += 1\n",
    "        # 遍历所有三元组\n",
    "        for i in range(1, n + 1):\n",
    "            for j in edge_l[i]:\n",
    "                for k in edge_l[j]:\n",
    "                    if k not in edge_l[i]:\n",
    "                        continue\n",
    "                    res = min(res, no_l[i] + no_l[j] + no_l[k] - 6)\n",
    "        return res if res != n * 3 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        # 定向后的图\n",
    "        h = defaultdict(set)\n",
    "        degree = [0] * (n+1)\n",
    "\n",
    "        for x, y in edges:\n",
    "            if x > y:\n",
    "                h[y].add(x)\n",
    "            else:\n",
    "                h[x].add(y)\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "        ans = 1200\n",
    "        for a in h.keys():\n",
    "            for b in h[a]:\n",
    "                for c in h.get(b, []):\n",
    "                    if c in h[a]:\n",
    "                        ans = min(ans, degree[a]+degree[b]+degree[c]-6)\n",
    "        if ans == 1200:\n",
    "            return -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        # 定向后的图\n",
    "        h = defaultdict(set)\n",
    "        degree = [0] * (n+1)\n",
    "\n",
    "        for x, y in edges:\n",
    "            if x > y:\n",
    "                x, y = y, x\n",
    "            h[x].add(y)\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "        ans = 1200\n",
    "        for a in h.keys():\n",
    "            for b in h[a]:\n",
    "                for c in h.get(b, []):\n",
    "                    if c in h[a]:\n",
    "                        ans = min(ans, degree[a]+degree[b]+degree[c]-6)\n",
    "        if ans == 1200:\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = math.inf\n",
    "        # g = [set() for _ in range(n)]\n",
    "        g = defaultdict(set)\n",
    "        cnt = [0] * n\n",
    "        for u, v in edges:\n",
    "            u -= 1\n",
    "            v -= 1\n",
    "            if u > v: u, v = v, u\n",
    "            g[u].add(v)\n",
    "            cnt[u] += 1\n",
    "            cnt[v] += 1\n",
    "\n",
    "        for i in range(n):\n",
    "            if len(g[i]) < 2: continue\n",
    "            for j in g[i]:\n",
    "                for k in g[j] & g[i]:\n",
    "                    ans = min(ans, cnt[i] + cnt[j] + cnt[k] - 6)\n",
    "\n",
    "        return -1 if ans == math.inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Itm:\n",
    "    def __init__(self, idx: int):\n",
    "        self.idx = idx\n",
    "        self.adj = set()\n",
    "        self.dgr = 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        S = [Itm(i) for i in range (n)]\n",
    "        res = 0xefffffff\n",
    "        for e in edges:\n",
    "            u, v = min(e) - 1, max(e) - 1\n",
    "            S[u].dgr += 1\n",
    "            S[v].dgr += 1\n",
    "            S[u].adj.add(v)\n",
    "        for i in range (n):\n",
    "            if S[i].dgr < 2:\n",
    "                continue\n",
    "            for j in S[i].adj:\n",
    "                if S[j].dgr < 2:\n",
    "                    continue\n",
    "                for k in S[j].adj:\n",
    "                    if S[k].dgr < 2:\n",
    "                        continue\n",
    "                    elif k in S[i].adj:\n",
    "                        res = min(S[i].dgr + S[j].dgr + S[k].dgr - 6, res)\n",
    "        if res == 0xefffffff:\n",
    "            return -1\n",
    "        else:\n",
    "            return res\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "#         g = [[] for _ in range(n + 1)]\n",
    "#         set_g = set()\n",
    "#         degree_g = [0] * (n + 1)\n",
    "#         ans = 16000\n",
    "#         for edge in edges:\n",
    "#             edge = tuple(sorted(edge))\n",
    "#             g[edge[0]].append(edge)\n",
    "#             set_g.add(edge)\n",
    "#             degree_g[edge[0]] += 1\n",
    "#             degree_g[edge[1]] += 1\n",
    "#         for v1, group in enumerate(g):\n",
    "#             for i, e1 in enumerate(group):\n",
    "#                 for j in range(i):\n",
    "#                     v2 = e1[1]\n",
    "#                     v3 = group[j][1]\n",
    "#                     if v3 < v2:\n",
    "#                         v2, v3 = v3, v2\n",
    "#                     e3 = (v2, v3)\n",
    "#                     if e3 in set_g:\n",
    "#                         ans = min(ans, degree_g[v1] + degree_g[v2] + degree_g[v3] - 6)\n",
    "#                         if ans == 0:\n",
    "#                             return 0\n",
    "#         return ans if ans < 16000 else -1\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        set_g = [set() for _ in range(n + 1)]\n",
    "        degree_g = [0] * (n + 1)\n",
    "        ans = 16000\n",
    "        for edge in edges:\n",
    "            degree_g[edge[0]] += 1\n",
    "            degree_g[edge[1]] += 1\n",
    "        for edge in edges:\n",
    "            edge = tuple(sorted(edge, key=lambda x:(degree_g[x], x)))\n",
    "            g[edge[0]].append(edge[1])\n",
    "            set_g[edge[0]].add(edge[1])\n",
    "        for v1, group in enumerate(g):\n",
    "            for i, v2 in enumerate(group):\n",
    "                for j in range(i):\n",
    "                    v3 = group[j]\n",
    "                    if v3 in set_g[v2] or v2 in set_g[v3]:\n",
    "                        ans = min(ans, degree_g[v1] + degree_g[v2] + degree_g[v3] - 6)\n",
    "                        if ans == 0:\n",
    "                            return 0\n",
    "        return ans if ans < 16000 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        if n < 3:\n",
    "            return -1\n",
    "\n",
    "        # nPairs[][0] - 顶点编号\n",
    "        # nPairs[][1] - 总边数\n",
    "        # nPairs[][2] - 后面的连通顶点\n",
    "        nPairs = [[i, 0, set()] for i in range(1,n+1)]\n",
    "        for u,v in edges:\n",
    "            nPairs[u-1][1] += 1\n",
    "            nPairs[v-1][1] += 1\n",
    "        for u,v in edges:\n",
    "            if (nPairs[u-1][1], nPairs[u-1][0]) < (nPairs[v-1][1], nPairs[v-1][0]):\n",
    "                nPairs[u-1][2].add(v)\n",
    "            else:\n",
    "                nPairs[v-1][2].add(u)\n",
    "        p2nPairs = [nPairs[i] for i in range(n)]\n",
    "        nPairs.sort(key=lambda x: (x[1], x[0]))\n",
    "\n",
    "        ind1 = 0\n",
    "        answer = -1\n",
    "\n",
    "        while ind1 <= n-3 and (answer == -1 \\\n",
    "        or answer > nPairs[ind1][1] + nPairs[ind1+1][1] + nPairs[ind1+2][1] - 6):\n",
    "            if len(nPairs[ind1][2]) < 2:\n",
    "                ind1 += 1\n",
    "                continue\n",
    "            \n",
    "            val1 = nPairs[ind1][1]\n",
    "            vers = list(nPairs[ind1][2])\n",
    "            vers.sort(key=lambda x: (p2nPairs[x-1][1], p2nPairs[x-1][0]))\n",
    "            vlen = len(vers)\n",
    "            ind2 = 0\n",
    "            val2 = p2nPairs[vers[ind2]-1][1]\n",
    "\n",
    "            while ind2 <= vlen-2 and (answer == -1 \\\n",
    "            or answer > val1 + val2 + p2nPairs[vers[ind2+1]-1][1] - 6):\n",
    "                indSet = p2nPairs[vers[ind2]-1][2]\n",
    "                for ver in vers[ind2+1:]:\n",
    "                    if ver in indSet and (answer == -1 \\\n",
    "                    or answer > val1 + val2 + p2nPairs[ver-1][1] - 6):\n",
    "                        answer = val1 + val2 + p2nPairs[ver-1][1] - 6\n",
    "                        break\n",
    "                ind2 += 1\n",
    "                val2 = p2nPairs[vers[ind2]-1][1]\n",
    "            \n",
    "            ind1 += 1\n",
    "        \n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        neighbors = defaultdict(set)\n",
    "        edges_count = defaultdict(int)\n",
    "        for a, b in edges:\n",
    "            edges_count[a] += 1\n",
    "            edges_count[b] += 1\n",
    "            if a > b:\n",
    "                neighbors[b].add(a)\n",
    "            else:\n",
    "                neighbors[a].add(b)\n",
    "\n",
    "        print(neighbors)\n",
    "        min_degree = inf\n",
    "        visited = set()\n",
    "        for node1 in range(1, n + 1):\n",
    "            for node2 in neighbors[node1]:\n",
    "                for node3 in neighbors[node1] & neighbors[node2]:\n",
    "                    # print(node1, node2, node3)\n",
    "                    min_degree = min(min_degree, edges_count[node1] + edges_count[node2] + edges_count[node3])\n",
    "        if min_degree == inf:\n",
    "            return -1\n",
    "        return min_degree - 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, es: List[List[int]]) -> int:\n",
    "        ind = [0] * n\n",
    "        st = set()\n",
    "        for [a, b] in es:\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            ind[a] += 1\n",
    "            ind[b] += 1\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            st.add(a * n + b)\n",
    "        res = 1000000000\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                a = i * n + j\n",
    "                if a not in st:\n",
    "                    continue\n",
    "                for k in range(j + 1, n):\n",
    "                    b = i * n + k\n",
    "                    c = j * n + k\n",
    "                    if b in st and c in st:\n",
    "                        res = min(res, ind[i] + ind[j] + ind[k] - 6)\n",
    "        if (res == 1000000000):\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        cnt = [0] * (n + 1)\n",
    "        ans = inf\n",
    "        for u, v in edges:\n",
    "            cnt[u] += 1\n",
    "            cnt[v] += 1\n",
    "            if u > v:\n",
    "                u, v = v, u\n",
    "            dic[u * 1000 + v] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                if dic[i * 1000 + j]:\n",
    "                    for k in range(j + 1, n + 1):\n",
    "                        if dic[i * 1000 + k] and dic[j * 1000 + k]:\n",
    "                            ans = min(ans, cnt[i] + cnt[j] + cnt[k] - 6)\n",
    "        return -1 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        E = [{} for i in range(n)]\n",
    "        for e in edges:\n",
    "            E[e[0]-1][e[1]-1] = 1\n",
    "            E[e[1]-1][e[0]-1] = 1\n",
    "        degrees = [len(sub) for sub in E]\n",
    "        res = float(\"inf\")\n",
    "        # print(E)\n",
    "        print(degrees)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                for k in range(j+1, n):\n",
    "                    if j in E[i] and k in E[j] and i in E[k]:\n",
    "                        # print(i, j, k)\n",
    "                        res = min(res, degrees[k]+degrees[j]+degrees[i]-6)\n",
    "        return res if res < float(\"inf\") else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        dd = defaultdict(int)\n",
    "        ss = set()\n",
    "        ds = defaultdict(set)\n",
    "        for item in edges:\n",
    "            dd[item[0]]+=1\n",
    "            dd[item[1]]+=1\n",
    "            \n",
    "            if item[0]<item[1]:\n",
    "                ds[item[0]].add(item[1])\n",
    "            else:\n",
    "                ds[item[1]].add(item[0])\n",
    "                item = [item[1], item[0]]\n",
    "        r = inf\n",
    "        edges.sort(key=lambda x:(dd[x[0]]+dd[x[1]]))\n",
    "        for item in edges:\n",
    "            if dd[item[0]]+dd[item[1]] >= r-2:\n",
    "                continue\n",
    "            for k in ds[item[1]]:\n",
    "                if k in ds[item[0]]:\n",
    "                    r = min(r, dd[k]+dd[item[0]]+dd[item[1]])\n",
    "        return r-6 if r<inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        b = [0] * (n + 1)\n",
    "        f = [[] for _ in range(n + 1)]\n",
    "        for x, y in edges:\n",
    "            b[x] += 1\n",
    "            b[y] += 1\n",
    "            f[x].append(y)\n",
    "            f[y].append(x)\n",
    "        h = [set() for _ in range(n + 1)]\n",
    "        for x, y in edges:\n",
    "            if b[x] < b[y] or (b[x] == b[y] and x < y):\n",
    "                h[x].add(y)\n",
    "            else:\n",
    "                h[y].add(x)\n",
    "        ans = inf\n",
    "        for i in range(1, n + 1):\n",
    "            for j in h[i]:\n",
    "                for k in h[j]:\n",
    "                    if k in h[i]:\n",
    "                        ans = min(b[i] + b[j] + b[k] - 6, ans)\n",
    "        return -1 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import sys\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        lines = [0] * 1000000\n",
    "        d = [0] * (n + 1)\n",
    "        for x, y in edges:\n",
    "            d[x] += 1\n",
    "            d[y] += 1\n",
    "            line = x * 1000 + y if x < y else y * 1000 + x\n",
    "            lines[line] = 1\n",
    "        \n",
    "        res = inf\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                if lines[i * 1000 + j]:\n",
    "                    for k in range(j + 1, n + 1):\n",
    "                        if lines[i * 1000 + k] and lines[j * 1000 + k]:\n",
    "                            res = min(res, d[i] + d[j] + d[k] - 6)\n",
    "        return -1 if res == inf else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        self.__DEBUG = False\n",
    "        INVALID = 2**30\n",
    "        def my_hash(i, j):\n",
    "            return i * 400 + j\n",
    "\n",
    "        hst = set()\n",
    "        min_ans = INVALID\n",
    "        deg = [0] * (n + 1)\n",
    "        for edge in edges:\n",
    "            edge = edge if edge[0] < edge[1] else [edge[1], edge[0]]\n",
    "            hst.add(my_hash(edge[0], edge[1]))\n",
    "            deg[edge[0]] += 1\n",
    "            deg[edge[1]] += 1\n",
    "        if self.__DEBUG:\n",
    "            print(hst)\n",
    "            print(deg)\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j + 1, n + 1):\n",
    "                    if ((my_hash(i, j) not in hst) \n",
    "                        or (my_hash(j, k) not in hst) \n",
    "                        or (my_hash(i, k) not in hst)\n",
    "                    ):\n",
    "                        continue\n",
    "                    if self.__DEBUG:\n",
    "                        print(i,j,k)\n",
    "\n",
    "                    tmp_ans = deg[i] + deg[j] + deg[k] - 6\n",
    "                    min_ans = min(min_ans, tmp_ans)\n",
    "        return -1 if min_ans == INVALID else min_ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        e = {}\n",
    "        d = {}\n",
    "        for u, v in edges:\n",
    "            if u not in e:\n",
    "                e[u] = {}\n",
    "                d[u] = 0\n",
    "            if v not in e:\n",
    "                e[v] = {}\n",
    "                d[v] = 0\n",
    "\n",
    "            e[u][v] = 1\n",
    "            e[v][u] = 1\n",
    "\n",
    "            d[u] += 1\n",
    "            d[v] += 1\n",
    "\n",
    "        \n",
    "        def calc(nodes):\n",
    "            res = 0\n",
    "            for n in nodes:\n",
    "                for p in e[n]:\n",
    "                    if p not in nodes:\n",
    "                        res += 1\n",
    "            return res\n",
    "        \n",
    "        res = -1\n",
    "        for a in e:\n",
    "            for b in e[a]:\n",
    "                if b < a: continue\n",
    "                for c in e[b]:\n",
    "                    if c < b: continue\n",
    "                    if c in e[a]:\n",
    "                        # d = calc([a, b, c])\n",
    "                        p = d[a] + d[b] + d[c] - 6\n",
    "                        if res == -1:\n",
    "                            res = p\n",
    "                        else:\n",
    "                            res = min(res, p)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        e = {}\n",
    "        d = {}\n",
    "        for u, v in edges:\n",
    "            if u not in e:\n",
    "                e[u] = {}\n",
    "                d[u] = 0\n",
    "            if v not in e:\n",
    "                e[v] = {}\n",
    "                d[v] = 0\n",
    "\n",
    "            e[u][v] = 1\n",
    "            e[v][u] = 1\n",
    "\n",
    "            d[u] += 1\n",
    "            d[v] += 1\n",
    "\n",
    "        \n",
    "        def calc(nodes):\n",
    "            res = 0\n",
    "            for n in nodes:\n",
    "                for p in e[n]:\n",
    "                    if p not in nodes:\n",
    "                        res += 1\n",
    "            return res\n",
    "        \n",
    "        res = -1\n",
    "        for a in e:\n",
    "            for b in e[a]:\n",
    "                if b < a: continue\n",
    "                for c in e[b]:\n",
    "                    if c < b: continue\n",
    "                    if c in e[a]:\n",
    "                        # d = calc([a, b, c])\n",
    "                        p = d[a] + d[b] + d[c] - 6\n",
    "                        if res == -1:\n",
    "                            res = p\n",
    "                        else:\n",
    "                            res = min(res, p)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        mat = [[0] * n for _ in range(n)]\n",
    "        degree = [0] * n\n",
    "        for i, j in edges:\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "            mat[i][j] = 1\n",
    "            mat[j][i] = 1\n",
    "            degree[i] += 1\n",
    "            degree[j] += 1\n",
    "        map = [[]  for _ in range(n)]\n",
    "        tmp_list = []\n",
    "        for i, j in edges:\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "            if degree[i] < degree[j]:\n",
    "                map[i].append(j)\n",
    "                tmp = (i, j)\n",
    "            elif degree[i] > degree[j]:\n",
    "                map[j].append(i)\n",
    "                tmp = (i, j)\n",
    "            elif i < j:\n",
    "                map[i].append(j)\n",
    "                tmp = (i, j)\n",
    "            else:\n",
    "                map[j].append(i)\n",
    "                tmp = (j, i)\n",
    "            tmp_list.append(tmp)\n",
    "        ret = inf = float('inf')\n",
    "        for i, j in tmp_list:\n",
    "            for k in map[j]:\n",
    "                if mat[k][i] and mat[k][j]:\n",
    "                    cur = degree[i] + degree[j] + degree[k]\n",
    "                    if cur < ret:\n",
    "                        ret = cur\n",
    "        if ret == inf:\n",
    "            return -1\n",
    "        return ret - 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        edge_dict = {}\n",
    "        degree=[0 for i in range(n+1)]\n",
    "        for edge in edges:\n",
    "            if(edge[0]<edge[1]):\n",
    "                edge_dict[ (edge[0],edge[1]) ]=1\n",
    "            else:\n",
    "                edge_dict[ (edge[1],edge[0]) ]=1\n",
    "            degree[edge[0]] += 1\n",
    "            degree[edge[1]] += 1\n",
    "        result = n*n*2\n",
    "        for i in range(1,n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if (i,j) not in edge_dict:\n",
    "                    continue\n",
    "                for k in range(j+1,n+1):\n",
    "                    if ((i,k) not in edge_dict) or ((j,k) not in edge_dict):\n",
    "                        continue\n",
    "                    if(degree[i]+degree[j]+degree[k]-6<result):\n",
    "                        result = degree[i]+degree[j]+degree[k]-6\n",
    "        if result == n*n*2:\n",
    "            return -1\n",
    "        else:\n",
    "            return result\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        edge_dict = dict()\n",
    "        vertex_dict = [[] for i in range(n)]\n",
    "        for edge in edges:\n",
    "            l, r = edge[0] - 1, edge[1] - 1\n",
    "            if l > r:\n",
    "                l, r = r, l\n",
    "            edge_dict[l * 400 + r] = 1\n",
    "            vertex_dict[l].append(r)\n",
    "            vertex_dict[r].append(l)\n",
    "        min_degree = 4000\n",
    "        vertex_dict = [sorted(vertex) for vertex in vertex_dict]\n",
    "\n",
    "        for i in range(n):\n",
    "            if len(vertex_dict[i]) > 1:\n",
    "                for j in range(len(vertex_dict[i])):\n",
    "                    if vertex_dict[i][j] <= i:\n",
    "                        continue\n",
    "                    for k in range(j + 1, len(vertex_dict[i])):\n",
    "                        idx, jdx, kdx = i, vertex_dict[i][j], vertex_dict[i][k]\n",
    "                        if (jdx * 400 + kdx) in edge_dict:\n",
    "                            min_degree = min(min_degree, len(vertex_dict[idx]) + len(vertex_dict[jdx]) + len(vertex_dict[kdx]) - 6)\n",
    "        if min_degree != 4000:\n",
    "            return min_degree\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        r = set([i+1 for i in range(n)])\n",
    "        indegree = [0 for i in range(n+1)]\n",
    "        for i, j in edges:\n",
    "            indegree[i] += 1\n",
    "            indegree[j] += 1\n",
    "        es = set()\n",
    "        for i, j in edges:\n",
    "            es.add((min(i, j), max(i, j)))\n",
    "        ans = inf\n",
    "        tri = set()\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i+1, n+1):\n",
    "                for k in range(j+1, n+1):\n",
    "                    if (i, j) in es and (j, k) in es and (i, k) in es:\n",
    "                        ans = min(ans, indegree[i] + indegree[j] + indegree[k] - 6)\n",
    "        if ans < inf:\n",
    "            return ans\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\r\n",
    "        from collections import defaultdict\r\n",
    "\r\n",
    "        connected = set()\r\n",
    "        degrees = defaultdict(int)\r\n",
    "        res = -1\r\n",
    "\r\n",
    "        for edge in edges:\r\n",
    "            connected.add(tuple(sorted(edge)))\r\n",
    "            for e in edge:\r\n",
    "                degrees[e] += 1\r\n",
    "\r\n",
    "        for i in range(1, n + 1):\r\n",
    "            if degrees[i] < 2:\r\n",
    "                continue\r\n",
    "            for j in range(i + 1, n + 1):\r\n",
    "                if degrees[j] < 2 or (i, j) not in connected:\r\n",
    "                    continue\r\n",
    "                for k in range(j + 1, n + 1):\r\n",
    "                    if degrees[k] < 2 or (j, k) not in connected or (i, k) not in connected:\r\n",
    "                        continue\r\n",
    "                    degree = degrees[i] + degrees[j] + degrees[k] - 6\r\n",
    "                    if res == -1 or res > degree:\r\n",
    "                        res = degree\r\n",
    "                        if res == 0:\r\n",
    "                            return 0\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        d = [0]*(n+1)\n",
    "\n",
    "        eset = set() #保存边\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            if edges[i][0]>edges[i][1]:\n",
    "                edges[i][0],edges[i][1] = edges[i][1],edges[i][0]\n",
    "            eset.add((edges[i][0],edges[i][1]))\n",
    "            d[edges[i][0]] += 1\n",
    "            d[edges[i][1]] += 1\n",
    "            \n",
    "        edges.sort()\n",
    "\n",
    "        #print(edges)\n",
    "        #print(eset)\n",
    "        #print(d)\n",
    "\n",
    "        mp = [None]\n",
    "        for _ in range(n):\n",
    "            mp.append([])\n",
    "\n",
    "        for e in edges:\n",
    "            mp[e[0]].append(e[1])\n",
    "        \n",
    "        #print(mp)\n",
    "        ret = float('inf')\n",
    "        for i in range(1,n+1):\n",
    "            for j in mp[i]:\n",
    "                for k in mp[j]:\n",
    "                    if (i,k) in eset:\n",
    "                        ret = min(d[i]+d[j]+d[k]-6,ret)\n",
    "                        if ret==0:\n",
    "                            return 0\n",
    "\n",
    "        if ret==float('inf'):\n",
    "            return -1\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "#         g = [[] for _ in range(n + 1)]\n",
    "#         set_g = set()\n",
    "#         degree_g = [0] * (n + 1)\n",
    "#         ans = 16000\n",
    "#         for edge in edges:\n",
    "#             edge = tuple(sorted(edge))\n",
    "#             g[edge[0]].append(edge)\n",
    "#             set_g.add(edge)\n",
    "#             degree_g[edge[0]] += 1\n",
    "#             degree_g[edge[1]] += 1\n",
    "#         for v1, group in enumerate(g):\n",
    "#             for i, e1 in enumerate(group):\n",
    "#                 for j in range(i):\n",
    "#                     v2 = e1[1]\n",
    "#                     v3 = group[j][1]\n",
    "#                     if v3 < v2:\n",
    "#                         v2, v3 = v3, v2\n",
    "#                     e3 = (v2, v3)\n",
    "#                     if e3 in set_g:\n",
    "#                         ans = min(ans, degree_g[v1] + degree_g[v2] + degree_g[v3] - 6)\n",
    "#                         if ans == 0:\n",
    "#                             return 0\n",
    "#         return ans if ans < 16000 else -1\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        set_g = [set() for _ in range(n + 1)]\n",
    "        degree_g = [0] * (n + 1)\n",
    "        ans = 16000\n",
    "        for edge in edges:\n",
    "            degree_g[edge[0]] += 1\n",
    "            degree_g[edge[1]] += 1\n",
    "        for edge in edges:\n",
    "            edge = tuple(sorted(edge, key=lambda x:(degree_g[x], x)))\n",
    "            g[edge[0]].append(edge[1])\n",
    "            set_g[edge[0]].add(edge)\n",
    "        for v1, group in enumerate(g):\n",
    "            for i, v2 in enumerate(group):\n",
    "                for j in range(i):\n",
    "                    v3 = group[j]\n",
    "                    if (v2, v3) in set_g[v2] or (v3, v2) in set_g[v3]:\n",
    "                        ans = min(ans, degree_g[v1] + degree_g[v2] + degree_g[v3] - 6)\n",
    "                        if ans == 0:\n",
    "                            return 0\n",
    "        return ans if ans < 16000 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        set_g = [set() for _ in range(n + 1)]\n",
    "        len_g = [0] * (n + 1)\n",
    "        ans = 16000\n",
    "        for edge in edges:\n",
    "            edge = tuple(sorted(edge))\n",
    "            g[edge[0]].append(edge)\n",
    "            set_g[edge[0]].add(edge)\n",
    "            len_g[edge[0]] += 1\n",
    "            len_g[edge[1]] += 1\n",
    "        for v1, group in enumerate(g):\n",
    "            for i, e1 in enumerate(group):\n",
    "                for j in range(i):\n",
    "                    v2 = e1[1]\n",
    "                    v3 = group[j][1]\n",
    "                    if v3 < v2:\n",
    "                        v2, v3 = v3, v2\n",
    "                    e3 = (v2, v3)\n",
    "                    if e3 in set_g[v2]:\n",
    "                        ans = min(ans, len_g[v1] + len_g[v2] + len_g[v3] - 6)\n",
    "                        if ans == 0:\n",
    "                            return 0\n",
    "        return ans if ans < 16000 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        degree: Dict[int, int] = defaultdict(int)\n",
    "        nextsGreater: Dict[int, Set[int]] = defaultdict(set)\n",
    "        nextsLess: Dict[int, Set[int]] = defaultdict(set)\n",
    "        # 每个节点的度数\n",
    "        for u, v in edges:\n",
    "            degree[u] += 1\n",
    "            degree[v] += 1\n",
    "            if u > v:\n",
    "                nextsGreater[v].add(u)\n",
    "                nextsLess[u].add(v)\n",
    "            else:\n",
    "                nextsGreater[u].add(v)\n",
    "                nextsLess[v].add(u)\n",
    "\n",
    "        ans: int = len(edges)\n",
    "        def findTrioMinDegree(first: int) -> None:\n",
    "            nonlocal ans\n",
    "            second: List[int] = nextsGreater[first]\n",
    "            for p in second:\n",
    "                for third in nextsGreater[p]:\n",
    "                    if first in nextsLess[third]:\n",
    "                        ans = min(ans, degree[first] + degree[p] + degree[third] - 6)\n",
    "        \n",
    "        for i in range(n):\n",
    "            findTrioMinDegree(i + 1)\n",
    "        \n",
    "        return ans if ans < len(edges) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "#         g = [[] for _ in range(n + 1)]\n",
    "#         set_g = set()\n",
    "#         degree_g = [0] * (n + 1)\n",
    "#         ans = 16000\n",
    "#         for edge in edges:\n",
    "#             edge = tuple(sorted(edge))\n",
    "#             g[edge[0]].append(edge)\n",
    "#             set_g.add(edge)\n",
    "#             degree_g[edge[0]] += 1\n",
    "#             degree_g[edge[1]] += 1\n",
    "#         for v1, group in enumerate(g):\n",
    "#             for i, e1 in enumerate(group):\n",
    "#                 for j in range(i):\n",
    "#                     v2 = e1[1]\n",
    "#                     v3 = group[j][1]\n",
    "#                     if v3 < v2:\n",
    "#                         v2, v3 = v3, v2\n",
    "#                     e3 = (v2, v3)\n",
    "#                     if e3 in set_g:\n",
    "#                         ans = min(ans, degree_g[v1] + degree_g[v2] + degree_g[v3] - 6)\n",
    "#                         if ans == 0:\n",
    "#                             return 0\n",
    "#         return ans if ans < 16000 else -1\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        set_g = set()\n",
    "        degree_g = [0] * (n + 1)\n",
    "        ans = 16000\n",
    "        for edge in edges:\n",
    "            degree_g[edge[0]] += 1\n",
    "            degree_g[edge[1]] += 1\n",
    "        for edge in edges:\n",
    "            edge = tuple(sorted(edge, key=lambda x:(degree_g[x], x)))\n",
    "            g[edge[0]].append(edge[1])\n",
    "            set_g.add(edge)\n",
    "        for v1, group in enumerate(g):\n",
    "            for i, v2 in enumerate(group):\n",
    "                for j in range(i):\n",
    "                    v3 = group[j]\n",
    "                    if (v2, v3) in set_g or (v3, v2) in set_g:\n",
    "                        ans = min(ans, degree_g[v1] + degree_g[v2] + degree_g[v3] - 6)\n",
    "                        if ans == 0:\n",
    "                            return 0\n",
    "        return ans if ans < 16000 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        info = {}\n",
    "        info2 = {}\n",
    "        for i in range(n):\n",
    "            info[i] = []\n",
    "            # info2[i] = set()\n",
    "            info2[i] = {}\n",
    "        \n",
    "        for edge in edges:\n",
    "            x, y = edge\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "            # print(x, y, info[y])\n",
    "            info[x].append(y)\n",
    "            info[y].append(x)\n",
    "            # info2[x].add(y)\n",
    "            # info2[y].add(x)\n",
    "            info2[x][y] = info2[x].get(y, 0) + 1\n",
    "            info2[y][x] = info2[y].get(x, 0) + 1\n",
    "        \n",
    "        res = n * n\n",
    "\n",
    "        for i in range(n):\n",
    "            info[i].sort()\n",
    "        \n",
    "        # print(info)\n",
    "        # print(info2)\n",
    "        for i in range(n):\n",
    "            for j in info[i]:\n",
    "                if i > j:\n",
    "                    continue\n",
    "                for t in info[j]:\n",
    "                    if j > t:\n",
    "                        continue\n",
    "                    if t in info2[i]:\n",
    "                        # print(res, info[i], info[j], info[t])\n",
    "                        # res = min(res, len(info[i]) + len(info[j]) + len(info[t]) - 6)\n",
    "                        res = min(res, len(info2[i]) + len(info2[j]) + len(info2[t]) - \\\n",
    "                        ((info2[i][j] + info2[i][t] + info2[j][t]) << 1))\n",
    "                        # ((len(info2[i] & info2[j]) + len(info2[i] & info2[t]) + len(info2[j] & info2[t])) << 1))\n",
    "\n",
    "        \n",
    "        # print(res, n)\n",
    "        return res if res < n * n else -1\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ##如何找三元组 ：  edges内， [a,b][b,c][a,c] 则abc就是三元组\n",
    "        #如何只遍历edges一遍就找出来：\n",
    "        #三元组中的每个点的组内连线有两条， 所以用 a点连线+b点连线+c点连线 - 6 = 三元组的度数\n",
    "        ## 400点，连满， 400*399 = 159,600条   任选三连组， 度数= 399*3 - 6 = 1191； 三元组共有 C(400, 3)个 \n",
    "        #= 400*399*398/6=10,586,800\n",
    "        #方法： 假设abc就是三元组   建立一个set 用来找[a,b][b,c][a,c] 一个Counter， Ca+Cb+Cc-6 = 度数\n",
    "        # ans = -1\n",
    "        # res = inf\n",
    "        setE = set(map(tuple,edges))   #set化，方便等下查找\n",
    "        a = []  #所有点的列表，用于Counter\n",
    "        for x in edges:\n",
    "            a += x\n",
    "        c = Counter(a)\n",
    "        ans = inf\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i+1, n+1):\n",
    "                for k in range(j+1, n+1):\n",
    "                    if ((i, j)  in setE or (j, i) in setE) and ((i, k)  in setE or (k, i) in setE) and ((j, k)  in setE or (k, j )in setE):\n",
    "                        res = c[i]+c[j]+c[k]-6\n",
    "                        ans = min(ans, res)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        degree = [0] * (n + 1)\n",
    "        edge_set = set()\n",
    "        for x, y in edges:\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "            edge_set.add((x, y) if x < y else (y, x))\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for x, y in edges:\n",
    "            x1, y1 = (x, y) if degree[x] < degree[y] or degree[x] == degree[y] and x < y else (y, x)\n",
    "            graph[x1].append(y1)\n",
    "        ans = len(edges) + 1\n",
    "        for x, y in edges:\n",
    "            for z in graph[y]:\n",
    "                if x == z:\n",
    "                    continue\n",
    "                x1, z1 = (x, z) if x < z else (z, x)\n",
    "                if (x1, z1) in edge_set:\n",
    "                    ans = min(ans, degree[x1] + degree[y] + degree[z1] - 6)\n",
    "        return ans if ans <= len(edges) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        degree = [0] * (n + 1)\n",
    "        edge_set = set()\n",
    "        for x, y in edges:\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "            edge_set.add((x, y) if x < y else (y, x))\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for x, y in edges:\n",
    "            x1, y1 = (x, y) if degree[x] < degree[y] or degree[x] == degree[y] and x < y else (y, x)\n",
    "            graph[x1].append(y1)\n",
    "        ans = len(edges) + 1\n",
    "        for x in range(1, n + 1):\n",
    "            for y in graph[x]:\n",
    "                for z in graph[y]:\n",
    "                    if x == z:\n",
    "                        continue\n",
    "                    x1, z1 = (x, z) if x < z else (z, x)\n",
    "                    if (x1, z1) in edge_set:\n",
    "                        ans = min(ans, degree[x1] + degree[y] + degree[z1] - 6)\n",
    "        return ans if ans <= len(edges) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        edges = sorted((min(i), max(i)) for i in edges)\n",
    "        s, d, res = set(edges), {i: [] for i in range(1, n+1)}, 99999999999\n",
    "        for u, v in edges:\n",
    "            d[u].append(v)\n",
    "            d[v].append(u)\n",
    "        for u in range(1, n-1):\n",
    "            for v in range(u+1, n):\n",
    "                for w in range(v+1, n+1):\n",
    "                    if (u, v) in s and (u, w) in s and (v, w) in s:\n",
    "                        res = min(res, len(d[w])+len(d[u])+len(d[v])-6)\n",
    "        return -1 if res == 99999999999 else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ginc = [set() for _ in range(n)]\n",
    "        gdec = [set() for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for x, y in edges:\n",
    "            x -= 1; y -= 1\n",
    "            if x > y:\n",
    "                x, y = y, x\n",
    "            ginc[x].add(y)\n",
    "            gdec[y].add(x)\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "\n",
    "        ans = -1\n",
    "        for x in range(n):\n",
    "            for y in ginc[x]:\n",
    "                for z in gdec[x]:\n",
    "                    if z in gdec[y]:\n",
    "                        cur = deg[x] + deg[y] + deg[z] - 6\n",
    "                        if ans == -1 or cur < ans:\n",
    "                            ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [set() for _ in range(n + 1)] \n",
    "        d = defaultdict(int)\n",
    "        for a, b in edges: \n",
    "            g[a].add(b)\n",
    "            g[b].add(a) \n",
    "            d[a] += 1 \n",
    "            d[b] += 1 \n",
    "        res = inf\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i + 1, n + 1): \n",
    "                for k in range(j + 1, n + 1):\n",
    "                    if j in g[i] and k in g[i] and k in g[j]: \n",
    "                        res = min(res, d[i] + d[j] + d[k] - 6) \n",
    "        return res if res != inf else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        degree=[0]*(n+1)\n",
    "        adlist=[set() for i in range(n+1)]\n",
    "        for x,y in edges:\n",
    "            degree[x]+=1\n",
    "            degree[y]+=1\n",
    "            adlist[x].add(y)\n",
    "            adlist[y].add(x)\n",
    "        ans=float('inf')\n",
    "        for i in range(1,n-1):\n",
    "            for j in adlist[i]:\n",
    "                if i>j:\n",
    "                    continue\n",
    "                for k in range(j+1,n+1):\n",
    "                    if i in adlist[k] and j in adlist[k]:\n",
    "                        ans=min(ans,degree[i]+degree[j]+degree[k])\n",
    "        return ans-6 if ans!=float('inf') else -1\n",
    "'''\n",
    "法一 暴力\n",
    "事先求所有点的度O(e)，以及邻接表（set实现以快速查连通性）\n",
    "枚举三个点\n",
    "检查他们是否联通，如果联通，则该三元组的度为三点总度-6\n",
    "时间复杂度O(n^3)枚举三个点O(n^3)\n",
    "空间复杂度O(n+e)记度和邻接表\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        degree=[0]*(n+1)\n",
    "        adlist=[set() for i in range(n+1)]\n",
    "        for x,y in edges:\n",
    "            degree[x]+=1\n",
    "            degree[y]+=1\n",
    "            adlist[x].add(y)\n",
    "            adlist[y].add(x)\n",
    "        ans=float('inf')\n",
    "        for i in range(1,n-1):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(j+1,n+1):\n",
    "                    if i in adlist[j] and i in adlist[k] and j in adlist[k]:\n",
    "                        ans=min(ans,degree[i]+degree[j]+degree[k])\n",
    "        return ans-6 if ans!=float('inf') else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        # 计算出入度。\n",
    "        # 无向边改为有向边。并且纳入hash。\n",
    "        degrees = defaultdict(int)\n",
    "        for edge in edges:\n",
    "            degrees[edge[0]] += 1\n",
    "            degrees[edge[1]] += 1\n",
    "\n",
    "        edge_hash = dict(zip(range(1, n+1), [[] for i in range(n)]))\n",
    "        for edge in edges:\n",
    "            i, j = edge[0], edge[1]\n",
    "            if degrees[i] < degrees[j]:\n",
    "                edge_hash[i].append(j)\n",
    "            elif degrees[i] == degrees[j]:\n",
    "                if i < j:\n",
    "                    edge_hash[i].append(j)\n",
    "                else:\n",
    "                    edge_hash[j].append(i)\n",
    "            else:\n",
    "                edge_hash[j].append(i)\n",
    "\n",
    "        # 然后是找出三元组。\n",
    "\n",
    "        check_edge = set([tuple(t) for t in edges])\n",
    "\n",
    "        ans = float(\"inf\")\n",
    "        for i, v in edge_hash.items():\n",
    "            for j in v:\n",
    "                for k in edge_hash[j]:\n",
    "                    if (i, k) in check_edge or (k, i) in check_edge:\n",
    "                        ans = min(degrees[i]+degrees[j]+degrees[k]-6, ans)\n",
    "\n",
    "        return ans if ans != float(\"inf\") else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minTrioDegree(self, n: int, edges: list[list[int]]) -> int:\r\n",
    "        # * 计算各边度数\r\n",
    "        degree = {i: set() for i in range(1, n+1)}\r\n",
    "        for x, y in edges:\r\n",
    "            degree[x].add(y)\r\n",
    "            degree[y].add(x)\r\n",
    "\r\n",
    "        ans = 10**9\r\n",
    "        # * 遍历所有临边\r\n",
    "        for a, b in edges:\r\n",
    "            for c in degree[a]:\r\n",
    "                if c > a and c > b and c in degree[b]:\r\n",
    "                    ans = min(ans, sum(len(degree[i]) for i in (a, b, c))-6)\r\n",
    "        return ans if ans != 10**9 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        linked = [set() for _ in range(n+1)]\n",
    "        for a, b in edges:\n",
    "            linked[a].add(b)\n",
    "            linked[b].add(a)\n",
    "        #print(linked)\n",
    "\n",
    "        mmin = len(edges)\n",
    "        for a, b in edges:\n",
    "            sa, sb = linked[a], linked[b]\n",
    "            for c in sa.intersection(sb):\n",
    "                sc = linked[c]\n",
    "                #print('try',a,b,c,sa,sb,sc,sa.union(sb,sc))\n",
    "                mmin = min(mmin, len(sa)+len(sb)+len(sc)-6)\n",
    "\n",
    "        return mmin if mmin != len(edges) else -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [set() for _ in range(n+1)]\n",
    "        for a, b in edges:\n",
    "            graph[a].add(b)\n",
    "            graph[b].add(a)\n",
    "        \n",
    "        ans = inf\n",
    "        for a in range(1, (n+2)//2+1):\n",
    "            for b in graph[a]:\n",
    "                if len(graph[a]) + len(graph[b]) - 4 >= ans:\n",
    "                    continue\n",
    "                possible = graph[a] & graph[b]\n",
    "                for c in possible:\n",
    "                    temp = len(graph[a]) + len(graph[b]) + len(graph[c]) - 6\n",
    "                    ans = min(ans, temp)\n",
    "                    if ans == 0:\n",
    "                        return ans\n",
    "        \n",
    "        return -1 if ans == inf else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        indegrees = collections.defaultdict(lambda: set())\n",
    "        res = float(\"inf\")\n",
    "        for u, v in edges:\n",
    "            indegrees[u].add(v)\n",
    "            indegrees[v].add(u)\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                for k in range(j + 1, n + 1):\n",
    "                    if j in indegrees[i] and k in indegrees[i] and k in indegrees[j]: \n",
    "                        d = len(indegrees[i]) + len(indegrees[j]) + len(indegrees[k]) - 6\n",
    "                        res = min(res, d)\n",
    "        return res if res != float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [set() for _ in range(n+1)]\n",
    "        for a, b in edges:\n",
    "            graph[a].add(b)\n",
    "            graph[b].add(a)\n",
    "        \n",
    "        ans = inf\n",
    "        for a in range(1, (n+2)//2+1):\n",
    "            if len(graph[a]) - 2 >= ans:\n",
    "                continue\n",
    "            for b in graph[a]:\n",
    "                if len(graph[a]) + len(graph[b]) - 4 >= ans or b < a:\n",
    "                    continue\n",
    "                possible = graph[a] & graph[b]\n",
    "                for c in possible:\n",
    "                    if c < a or c < b:\n",
    "                        continue\n",
    "                    temp = len(graph[a]) + len(graph[b]) + len(graph[c]) - 6\n",
    "                    ans = min(ans, temp)\n",
    "                    if ans == 0:\n",
    "                        return ans\n",
    "        \n",
    "        return -1 if ans == inf else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 另一种将无向图根据条件转化为有向图从而限制枚举次数与边数关联的枚举三元组方式\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    INF = 10 ** 9\n",
    "\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        g = [set() for _ in range(n + 1)]\n",
    "        deg = [0 for _ in range(n + 1)]\n",
    "        for u, v in edges:\n",
    "            g[u].add(v)\n",
    "            g[v].add(u)\n",
    "            deg[u] += 1\n",
    "            deg[v] += 1\n",
    "\n",
    "        h = [[] for _ in range(n + 1)]\n",
    "        for u,  v in edges:\n",
    "            if deg[u] > deg[v]:\n",
    "                u, v = v, u\n",
    "            h[u].append(v)\n",
    "\n",
    "        ans = Solution.INF\n",
    "        for i in range(1, n + 1):\n",
    "            for j in h[i]:\n",
    "                for k in h[j]:\n",
    "                    if k in g[i]:\n",
    "                        ans = min(ans, deg[i] + deg[j] + deg[k])\n",
    "\n",
    "        return ans - 6 if ans < Solution.INF else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        d = set()\n",
    "        u = [0]*n\n",
    "        for i, j in edges:\n",
    "            if i > j:\n",
    "                d.add((j, i))\n",
    "            else:\n",
    "                d.add((i, j))\n",
    "            u[i - 1] += 1\n",
    "            u[j - 1] += 1\n",
    "        res = math.inf\n",
    "        #print(u)\n",
    "        edges.sort(key=lambda x: u[x[0] - 1] + u[x[1] - 1])\n",
    "        s = sorted([i for i in range(n)], key=lambda x: u[x])\n",
    "        #print(edges)\n",
    "        for i, j in edges:\n",
    "            for k in s:\n",
    "                if ((k + 1, i) in d or (i, k + 1) in d) and ((k + 1, j) in d or (j, k + 1) in d):\n",
    "                    #print(i - 1, j - 1, k)\n",
    "                    res = min(u[i - 1] + u[j - 1] + u[k] - 6, res)\n",
    "                    break\n",
    "        return res if res != math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        edge_dict= defaultdict(set)\n",
    "        degrees=defaultdict(int)\n",
    "        for p,q in edges:\n",
    "            edge_dict[p].add(q)\n",
    "            edge_dict[q].add(p)\n",
    "            degrees[p]+=1\n",
    "            degrees[q]+=1\n",
    "        edges_iter={}\n",
    "        for i in edge_dict:\n",
    "            edges_iter[i]=list(sorted(edge_dict[i],key=lambda x:degrees[x]))\n",
    "        ret=math.inf\n",
    "        for i in edge_dict:\n",
    "            for j in edge_dict[i]:\n",
    "                for k in edges_iter[j]:\n",
    "                    if i in edge_dict[k]:\n",
    "                        ret=min(ret,degrees[i]-2+degrees[j]-2+degrees[k]-2)\n",
    "                        break\n",
    "        return ret if ret!=math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g=defaultdict(list)\n",
    "        ck=defaultdict(set)\n",
    "        for x,y in edges:\n",
    "            if x<y:\n",
    "                g[x].append(y)\n",
    "            else:\n",
    "                g[y].append(x)\n",
    "            ck[x].add(y)\n",
    "            ck[y].add(x)\n",
    "        \n",
    "        res=len(edges)+1\n",
    "        for i in range(1,n+1):\n",
    "            for j in g[i]:\n",
    "                for k in g[j]:\n",
    "                    if k not in ck[i]:\n",
    "                        continue\n",
    "                    res=min(res,len(ck[i])+len(ck[j])+len(ck[k])-6)\n",
    "\n",
    "        return res if res<len(edges)+1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        d = {}\n",
    "        for edge in edges:\n",
    "            x, y = edge\n",
    "            if x not in d:\n",
    "                d[x] = []\n",
    "            d[x].append(y)\n",
    "            if y not in d:\n",
    "                d[y] = []\n",
    "            d[y].append(x)\n",
    "        # print(d)\n",
    "        result = n * n\n",
    "        hit = False\n",
    "\n",
    "        ds = {}\n",
    "        for v1, l in d.items():\n",
    "            ds[v1] = set(l)\n",
    "        for v1, l in d.items():\n",
    "            l.sort()\n",
    "\n",
    "        for v1, l in d.items():\n",
    "            v1_out = len(d[v1])\n",
    "            if v1_out < 2:\n",
    "                continue\n",
    "            for i in range(len(l)):\n",
    "                v2 = l[i]\n",
    "                if v2 < v1:\n",
    "                    continue\n",
    "                v2_out = len(d[v2])\n",
    "                if v2_out < 2:\n",
    "                    continue\n",
    "                for j in range(i+1, len(l)):\n",
    "                    v3 = l[j]\n",
    "                    if v3 < v2:\n",
    "                        continue\n",
    "                    if v2 not in ds[v3]:\n",
    "                        continue\n",
    "                    # print(v1, v2, v3)\n",
    "                    v3_out = len(d[v3])\n",
    "                    result = min(result, v1_out + v2_out + v3_out - 6)\n",
    "                    # print(v1_out, v2_out, v3_out)\n",
    "                    hit = True\n",
    "        if not hit:\n",
    "            return -1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        deg = [0] * n\n",
    "        g = defaultdict(list)\n",
    "        s = set((x - 1, y - 1) for x, y in edges)\n",
    "        for x, y in edges:\n",
    "            x, y = sorted([x, y])\n",
    "            deg[x - 1] += 1\n",
    "            deg[y - 1] += 1\n",
    "            g[x - 1].append(y - 1)\n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            li = g[i]\n",
    "            m = len(g[i])\n",
    "            for j in range(m):\n",
    "                nj = li[j]\n",
    "                for k in range(j + 1, m):\n",
    "                    nk = li[k]\n",
    "                    if (nj, nk) in s or (nk, nj) in s:\n",
    "                        ans = min(ans, deg[i] + deg[nj] + deg[nk] - 6)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g=[set() for i in range(n)]\n",
    "        for i,o in edges:\n",
    "            g[i-1].add(o-1)\n",
    "            g[o-1].add(i-1)\n",
    "        res=2**31-1\n",
    "        def get_degree(i,j,k):\n",
    "            return len(g[i])+len(g[j])+len(g[k])-6\n",
    "        for i in range(n):\n",
    "            for j in g[i]:\n",
    "                if j<i:\n",
    "                    continue\n",
    "                t=g[i]&g[j]\n",
    "                for k in t:\n",
    "                    if k<i or k<j:\n",
    "                        continue\n",
    "                    res=min(res,get_degree(i,j,k))\n",
    "        return res if res!=2**31-1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        degree = [0] * n\n",
    "        points = defaultdict(set)\n",
    "        for edge in edges:\n",
    "            degree[edge[0]-1] += 1\n",
    "            degree[edge[1]-1] += 1\n",
    "            points[edge[0]-1].add(edge[1]-1)\n",
    "            points[edge[1]-1].add(edge[0]-1)\n",
    "        v_p = [i for i, d in enumerate(degree) if d >= 2]\n",
    "        res = float('inf')\n",
    "\n",
    "        for i in v_p:\n",
    "            s = points[i]\n",
    "            l = list(s)\n",
    "            for j in range(0, len(l)):\n",
    "                for k in range(j+1, len(l)):\n",
    "                    if l[j] in points[l[k]]:\n",
    "                        res = min(res, degree[i] + degree[l[j]] + degree[l[k]] - 6)\n",
    "            for j in range(0, len(l)):\n",
    "                points[l[j]].remove(i)\n",
    "        if res == float('inf'):\n",
    "            res = -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "      graph = defaultdict(set)\n",
    "\n",
    "      for x, y in edges:\n",
    "        graph[x - 1].add(y - 1)\n",
    "        graph[y - 1].add(x - 1)\n",
    "\n",
    "      res = float(\"inf\")\n",
    "      for i in range(n - 2):\n",
    "        for j in range(i + 1, n - 1):\n",
    "          if j not in graph[i]:\n",
    "            continue\n",
    "          for k in range(j + 1, n):\n",
    "            if k not in graph[i] or k not in graph[j]:\n",
    "              continue\n",
    "            # print(f\"i = {(i, len(graph[i]))}, j = {(j, len(graph[j]))}, k = {(k, len(graph[k]))}\")\n",
    "            res = min(res, len(graph[i]) + len(graph[j]) + len(graph[k]) - 6)\n",
    "            if res == 0:\n",
    "              return 0\n",
    "\n",
    "      return res if res != float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        e=collections.defaultdict(set)\n",
    "        v=set()\n",
    "        for e1,e2 in edges:\n",
    "            e[e1].add(e2)\n",
    "            e[e2].add(e1)\n",
    "            v.add(e1)\n",
    "            v.add(e2)\n",
    " \n",
    "        def dfs(u,root,father,n,order):\n",
    "            #print(u,root,father,n,order,len(e[u]))\n",
    "            u_order=len(e[u])\n",
    "            if u_order<=1:\n",
    "                return float(\"inf\")\n",
    "            if n==2:\n",
    "                if root in e[u]:\n",
    "                    return order+u_order-6\n",
    "                else:\n",
    "                    return float(\"inf\")\n",
    "            res=float(\"inf\")\n",
    "            for child in e[u]:\n",
    "                if child==father:continue\n",
    "                if father and child<father:continue\n",
    "                if child<root:continue\n",
    "                res=min(res,dfs(child,root,u,n+1,order+u_order))\n",
    "            return res\n",
    "        \n",
    "        res=float(\"inf\")\n",
    "        for u in v:\n",
    "            res=min(res,dfs(u,u,None,0,0))\n",
    "        return res if res!=float(\"inf\") else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # a - b (c in a and c in b)\n",
    "        g = [set() for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        ans = inf\n",
    "        vis = [[False] * n for _ in range(n)]\n",
    "        for u in range(n):\n",
    "            # if u in vis: continue\n",
    "            for v in g[u]:\n",
    "                if vis[u][v] or vis[v][u]: continue\n",
    "                vis[u][v], vis[v][u] = True, True\n",
    "                for w in g[v]:\n",
    "                    if w in g[u]: ans = min(ans, len(g[u]) + len(g[v]) + len(g[w]) - 6)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        res=(n+1)**2\n",
    "        md=1000\n",
    "        cnt=[0 for _ in range(0,n+1)]\n",
    "        edges=[[min(i[0],i[1]),max(i[0],i[1])] for i in edges]\n",
    "        edges.sort(key=lambda x:x[0]*md+x[1])\n",
    "        pts={}\n",
    "        cp=set()\n",
    "        for i in edges:\n",
    "            if i[0] not in pts.keys():\n",
    "                pts[i[0]]=[]\n",
    "            pts[i[0]].append(i[1])\n",
    "            cnt[i[0]]+=1\n",
    "            cnt[i[1]]+=1\n",
    "            cp.add(i[0]*md+i[1])\n",
    "        for i in range(1,n+1):\n",
    "            if cnt[i]<=0:\n",
    "                continue\n",
    "            if i in pts.keys() and len(pts[i])>=2:\n",
    "                m=len(pts[i])\n",
    "                for j in range(0,m-1):\n",
    "                    for k in range(j,m):\n",
    "                        if pts[i][j]*md+pts[i][k] in cp:\n",
    "                            v=cnt[i]+cnt[pts[i][j]]+cnt[pts[i][k]]-6\n",
    "                            res=min(res,v)\n",
    "        return res if res!=(n+1)**2 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [set() for _ in range(n)]\n",
    "        gg = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            i, j = i - 1, j - 1\n",
    "            g[i].add(j)\n",
    "            g[j].add(i)\n",
    "            if i > j:\n",
    "                i, j = j, i\n",
    "            gg[i].append(j)\n",
    "    \n",
    "        si = [[len(x), idx] for idx, x in enumerate(g)]\n",
    "        m = 10000000\n",
    "        for idx, v in enumerate(gg):\n",
    "            if len(v) <= 1:\n",
    "                continue\n",
    "            v = sorted(v)\n",
    "            for i in range(len(v) - 1):\n",
    "                for j in range(i + 1, len(v)):\n",
    "                    a = v[i]\n",
    "                    b = v[j]\n",
    "                    if b in g[a]:\n",
    "                        m = min(si[a][0] + si[b][0] + si[idx][0] - 6, m)\n",
    "        return m if m < 10000000 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        r_set = [set() for _ in range(n)]\n",
    "        inc_r_next = [[] for _ in range(n)]\n",
    "        degree = [0] * n\n",
    "        ans = 10000\n",
    "        for x, y in edges:\n",
    "            x= x-1\n",
    "            y=y-1\n",
    "            if x > y: \n",
    "                y, x = x, y\n",
    "            r_set[x].add(y)\n",
    "            r_set[y].add(x)\n",
    "            inc_r_next[x].append(y)\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "        for i in range(n):\n",
    "            for j in inc_r_next[i]:\n",
    "                for h in inc_r_next[j]:\n",
    "                    if h in r_set[i]:\n",
    "                        ans = min(ans, degree[i]+degree[j] + degree[h] - 6)\n",
    "        return -1 if ans == 10000 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        conn = [set() for _ in range(n)]\n",
    "        degree = [0 for _ in range(n)]\n",
    "        directed = [set() for _ in range(n)]\n",
    "        for i in range(len(edges)):\n",
    "            edges[i][0] -= 1\n",
    "            edges[i][1] -= 1\n",
    "            conn[edges[i][0]].add(edges[i][1])\n",
    "            conn[edges[i][1]].add(edges[i][0])\n",
    "            degree[edges[i][0]] += 1\n",
    "            degree[edges[i][1]] += 1\n",
    "        for u, v in edges:\n",
    "            if degree[u] < degree[v] or degree[u] == degree[v] and u < v:\n",
    "                directed[u].add(v)\n",
    "            else:\n",
    "                directed[u].add(v)\n",
    "        res = -1\n",
    "        for p1 in range(n):\n",
    "            for p2 in directed[p1]:\n",
    "                inters = conn[p1].intersection(conn[p2])\n",
    "                for p3 in inters:\n",
    "                    d = len(conn[p1]) + len(conn[p2]) + len(conn[p3]) - 6\n",
    "                    if res == -1 or res > d:\n",
    "                        res = d\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        d = [0] * n\n",
    "        neibors = [set() for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            d[i-1] += 1\n",
    "            d[j-1] += 1\n",
    "            neibors[i-1].add(j-1)\n",
    "            neibors[j-1].add(i-1)\n",
    "        h = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            if d[i-1] < d[j-1]:\n",
    "                h[i-1].append(j-1)\n",
    "            elif d[i-1] > d[j-1]:\n",
    "                h[j-1].append(i-1)\n",
    "            elif i < j:\n",
    "                h[i-1].append(j-1)\n",
    "            else:\n",
    "                h[j-1].append(i-1)\n",
    "        ans = float('inf')\n",
    "        for i in range(n):\n",
    "            for j in h[i]:\n",
    "                for k in h[j]:\n",
    "                    if i in neibors[k]:\n",
    "                        ans = min(ans, d[i]+d[j]+d[k]-6)\n",
    "        return ans if ans != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 原图\n",
    "        g = defaultdict(set)\n",
    "        # 定向后的图\n",
    "        h = defaultdict(list)\n",
    "        degree = [0] * n\n",
    "\n",
    "        for x, y in edges:\n",
    "            x, y = x - 1, y - 1\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "        \n",
    "        for x, y in edges:\n",
    "            x, y = x - 1, y - 1\n",
    "            if degree[x] < degree[y] or (degree[x] == degree[y] and x < y):\n",
    "                h[x].append(y)\n",
    "            else:\n",
    "                h[y].append(x)\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            for j in h[i]:\n",
    "                for k in h[j]:\n",
    "                    if k in g[i]:\n",
    "                        ans = min(ans, degree[i] + degree[j] + degree[k] - 6)\n",
    "\n",
    "        return -1 if ans == inf else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 原图\n",
    "        g = defaultdict(set)\n",
    "        # 定向后的图\n",
    "        h = defaultdict(list)\n",
    "        degree = [0] * n\n",
    "\n",
    "        for x, y in edges:\n",
    "            x, y = x - 1, y - 1\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "        \n",
    "        for x, y in edges:\n",
    "            x, y = x - 1, y - 1\n",
    "            if degree[x] < degree[y] or (degree[x] == degree[y] and x < y):\n",
    "                h[x].append(y)\n",
    "            else:\n",
    "                h[y].append(x)\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            for j in h[i]:\n",
    "                for k in h[j]:\n",
    "                    if k in g[i]:\n",
    "                        ans = min(ans, degree[i] + degree[j] + degree[k] - 6)\n",
    "\n",
    "        return -1 if ans == inf else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 原图\n",
    "        g = defaultdict(set)\n",
    "        # 定向后的图\n",
    "        h = defaultdict(list)\n",
    "        degree = [0] * n\n",
    "\n",
    "        for x, y in edges:\n",
    "            x, y = x - 1, y - 1\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "        \n",
    "        for x, y in edges:\n",
    "            x, y = x - 1, y - 1\n",
    "            if degree[x] < degree[y] or (degree[x] == degree[y] and x < y):\n",
    "                h[x].append(y)\n",
    "            else:\n",
    "                h[y].append(x)\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            for j in h[i]:\n",
    "                for k in h[j]:\n",
    "                    if k in g[i]:\n",
    "                        ans = min(ans, degree[i] + degree[j] + degree[k] - 6)\n",
    "\n",
    "        return -1 if ans == inf else ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
